#include <vector>

using namespace std;


/**
 * @brief 巧妙解法：从左下角开始，这样小于的都在纵向上，大于的都在横向右
 *        巧妙利用数组递增特性与查找方向！
 *        O(M+N)
 */
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int m = array.size();
        if (m == 0) return false;
        int n = array[0].size();
        if (n == 0) return false;
        
        // Start from the lower left corner
        int i = m-1;
        int j = 0;
        while (i >= 0 && j < n) {
            if (array[i][j] == target) return true;
            else if (array[i][j] < target) j++;
            else i--;
        }
        return false;
    }
};
